package com.cat.slidingWindow;

import java.util.Map;
import java.util.TreeMap;

/**
 * @author cat
 * @description https://leetcode.cn/problems/sliding-subarray-beauty/
 * @create 2025/7/28 09:13
 * @since JDK17
 */

public class Solution04 {
    TreeMap<Integer, Integer> map = new TreeMap<>();
    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        int n = nums.length, cnt;
        int[] ans = new int[n - k + 1];
        for (int i = 0; i < k - 1; i++) { // 先加入k个数字
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        // 定长窗口
        for (int l = 0, r = k - 1, j; r < n; r++, l++) {
            map.put(nums[r], map.getOrDefault(nums[r], 0) + 1);

            j = x;
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                j -= entry.getValue();
                if (j <= 0) {
                    if (entry.getKey() < 0) {
                        ans[l] = entry.getKey();
                    } else {
                        ans[l] = 0;
                    }
                    break;
                }
            }
            cnt = map.get(nums[l]) - 1; // 获取当前数字的数量
            if (cnt == 0) {
                map.remove(nums[l]);
            } else {
                map.put(nums[l], cnt);
            }
        }
        map.clear();
        return ans;
    }
}
